//https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/572657562/
class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 1, right = 1000000000;
        while (left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            int count = 1;
            int t = position[0];
            for (int i = 1; i < position.size(); ++i)
            {
                if (position[i] - t >= mid) { count++; t = position[i]; };
            }
            if (count >= m)left = mid;
            else right = mid - 1;
        }
        return left;
    }
};